package com.tys.algorithm.advanced.code.class19;

import java.util.HashMap;

/**
 * 剪字符串拼字符串
 * 给定一个字符串str, 给定一个字符串类型的数组arr，出现的字符都是小写英文
 * arr每一个字符串，代表一张贴纸，你可以把单个字符剪开使用，
 * 目的是拼出str来，返回需要至少多少张贴纸可以完成这个任务
 * 例子：str="babac" arr={"ba","c","abcd"}
 * 贴纸个数是无群张
 * ba + ba + c 需要 3 张
 * ba + abcd 需要 2 张
 * abcd + abcd 需要 2 张
 * 至少需要两张贴纸"ba"和“abcd"，因为使用者两张贴纸，
 * 把每一个字符单独剪开，含有2个a，2个b，1个c，是可以拼出str的，所以返回2
 * <p>
 * 本题测试链接：https://leetcode.com/problems/stickers-to-spell-word
 */
public class Code03_StickersToSpellWord {

    public static int minStickers1(String[] stickers, String target) {
        int ans = process1(stickers, target);
        //-1代表弄不完
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }

    // stickers：所有贴纸，每一种贴纸都有无穷张
    // target：目标
    // 返回：最少张数
    public static int process1(String[] stickers, String target) {
        //没东西了：0张
        if (target.length() == 0) {
            return 0;
        }
        //系统最大值
        int min = Integer.MAX_VALUE;
        //每张作为第一张时
        for (String first : stickers) {
            //减字符后剩余的
            String rest = minus(target, first);
            //贴纸中有目标中的字母
            if (rest.length() != target.length()) {
                //得到后续最小的个数
                min = Math.min(min, process1(stickers, rest));
            }
        }
        //搞不定就返回系统最大值
        //有小的则+1
        return min + (min == Integer.MAX_VALUE ? 0 : 1);
    }

    //s1：目标
    //s2：贴纸
    //返回：目标-贴纸中出现过的字母，剩余的字母组成的字符串
    public static String minus(String s1, String s2) {
        char[] str1 = s1.toCharArray();
        char[] str2 = s2.toCharArray();
        int[] count = new int[26];
        //将s1目标中中包含的字母计数：+1
        for (char cha : str1) {
            count[cha - 'a']++;
        }
        //将s2贴纸中包含的字母也计数：-1
        for (char cha : str2) {
            count[cha - 'a']--;
        }
        //将剩余的字母重新组成一个字符串返回
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < 26; i++) {
            //剩余的
            if (count[i] > 0) {
                //剩的数量
                for (int j = 0; j < count[i]; j++) {
                    //字母追加入builder中
                    builder.append((char) (i + 'a'));
                }
            }
        }
        //返回新的
        return builder.toString();
    }

    //方法2：词频表+剪枝
    public static int minStickers2(String[] stickers, String target) {
        int N = stickers.length;
        // 关键优化(用词频表替代贴纸数组)：[贴纸编码][字母个数]
        int[][] counts = new int[N][26];
        //生成词频统计表：将字符串数组转为二维数组
        for (int i = 0; i < N; i++) { //遍历贴纸数组
            char[] str = stickers[i].toCharArray(); //将贴纸转为字符数组
            for (char cha : str) { //遍历字符数组
                counts[i][cha - 'a']++;
            }
        }
        int ans = process2(counts, target);
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }

    // stickers：所有贴纸，stickers[i] 数组，当初i号贴纸的字符统计
    // int[][] stickers -> 所有的贴纸
    // 每一种贴纸都有无穷张
    // 返回搞定target的最少张数
    // 最少张数
    public static int process2(int[][] stickers, String t) {
        //没有字符了0张
        if (t.length() == 0) {
            return 0;
        }
        // target做出词频统计
        // target  aabbc  2 2 1..
        //                0 1 2..
        char[] target = t.toCharArray();
        int[] tcounts = new int[26];
        //词频统计
        for (char cha : target) {
            tcounts[cha - 'a']++;
        }
        int N = stickers.length;
        int min = Integer.MAX_VALUE; //最小张数
        for (int i = 0; i < N; i++) {
            // 尝试第一张贴纸是谁
            int[] sticker = stickers[i];
            // 最关键的优化(重要的剪枝!这一步也是贪心!)
            // 如果target[0]位置的字符在贴纸中则处理
            if (sticker[target[0] - 'a'] > 0) {
                StringBuilder builder = new StringBuilder();
                for (int j = 0; j < 26; j++) { //26个字符
                    if (tcounts[j] > 0) {
                        //目标字符个数 - 贴纸字符个数
                        int nums = tcounts[j] - sticker[j];
                        //剩余的保留到builder
                        for (int k = 0; k < nums; k++) {
                            builder.append((char) (j + 'a'));
                        }
                    }
                }
                String rest = builder.toString();
                //关注最小
                min = Math.min(min, process2(stickers, rest));
            }
        }
        return min + (min == Integer.MAX_VALUE ? 0 : 1);
    }

    //方法3：加缓存表
    public static int minStickers3(String[] stickers, String target) {
        int N = stickers.length;
        int[][] counts = new int[N][26];
        for (int i = 0; i < N; i++) {
            char[] str = stickers[i].toCharArray();
            for (char cha : str) {
                counts[i][cha - 'a']++;
            }
        }
        HashMap<String, Integer> dp = new HashMap<>();
        dp.put("", 0);
        int ans = process3(counts, target, dp);
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }

    //加缓存dp
    public static int process3(int[][] stickers, String t, HashMap<String, Integer> dp) {
        //缓存有记录直接返回
        if (dp.containsKey(t)) {
            return dp.get(t);
        }
        char[] target = t.toCharArray();
        int[] tcounts = new int[26];
        for (char cha : target) {
            tcounts[cha - 'a']++;
        }
        int N = stickers.length;
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < N; i++) {
            int[] sticker = stickers[i];
            if (sticker[target[0] - 'a'] > 0) {
                StringBuilder builder = new StringBuilder();
                for (int j = 0; j < 26; j++) {
                    if (tcounts[j] > 0) {
                        int nums = tcounts[j] - sticker[j];
                        for (int k = 0; k < nums; k++) {
                            builder.append((char) (j + 'a'));
                        }
                    }
                }
                String rest = builder.toString();
                min = Math.min(min, process3(stickers, rest, dp));
            }
        }
        int ans = min + (min == Integer.MAX_VALUE ? 0 : 1);
        //放入缓存
        dp.put(t, ans);
        return ans;
    }

}
